package com.atguigui.leetcode;

/**
 * 707.设计链表
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/9/23 8:28
 */
public class P707DesignLinkedList {

    public static void main(String[] args) {
        MyLinkedList solution = new P707DesignLinkedList().new MyLinkedList();
        // TO TEST
    }

    class MyLinkedList {

        int size;
        ListNode head;

        public MyLinkedList() {
            this.size = 0;
            this.head = new ListNode(0);
        }

        //获取链表中第 index 个节点的值。如果索引无效，则返回-1
        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode cur = head;
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }

        //在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点
        public void addAtHead(int val) {
            addAtIndex(0, val);
        }

        //将值为 val 的节点追加到链表的最后一个元素
        public void addAtTail(int val) {
            addAtIndex(size, val);
        }

        //在链表中的第index个节点之前添加值为val 的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
        public void addAtIndex(int index, int val) {
            if (index > size) {
                return;
            }
            index = Math.max(0, index);
            size++;
            ListNode pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            //新节点
            ListNode toAdd = new ListNode(val);
            toAdd.next = pred.next;
            pred.next = toAdd;
        }

        //如果索引 index 有效，则删除链表中的第 index 个节点
        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }
            size--;
            ListNode pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            pred.next = pred.next.next;
        }


        class ListNode {
            int val;
            ListNode next;

            public ListNode(int val) {
                this.val = val;
            }
        }
    }


}
